package com.二叉树.动态二叉树;
import com.二叉树.动态二叉树.*;


public class dyncTreeDemo {
    /**
     * 创建二叉查找树
     * @param rootTree
     * @param value
     */
    public static void createTree(RootTree rootTree,int value){
        //判断根节点是否为空
        if(rootTree.getRootTree() == null){
            rootTree.setRootTree(new TreeNode(value));
        }else{
            //获取当前根切点
            TreeNode pre = rootTree.getRootTree();

           while(pre != null){
               //往右边走
               if(value > pre.getValue()){
                   //没有树根直接插入
                   if(pre.getRightNode()==null){
                       pre.setRightNode(new TreeNode(value));
                       return;
                   }else{
                       //有树根继续往右边走
                       pre = pre.getRightNode();
                   }
               }else{
                   //左节点 往左走
                   if(pre.getLeftTreeNode() == null){
                       pre.setLeftTreeNode(new TreeNode(value));
                       return;
                   }else{
                       pre = pre.getLeftTreeNode();
                   }
               }
           }
        }
        System.out.println("创建成功");
    }
    /**
     * 先序遍历
     * @param rootNode
     */
    public static void before(TreeNode rootNode){
        if(rootNode == null){
            return;
        }
        //根节点
        System.out.println(rootNode.getValue());
        //左节点
        before(rootNode.getLeftTreeNode());
        //右节点
        before(rootNode.getRightNode());
    }

    /**
     * 中序遍历
     * @param
     */
    public static void between(TreeNode rootNode){
        if(rootNode == null){
            return;
        }
        between(rootNode.getLeftTreeNode());
        System.out.println(rootNode.getValue());
        between(rootNode.getRightNode());
    }

    /**
     * 后序遍历
     * @param rootNode
     */
    public static  void after(TreeNode rootNode){
        if(rootNode == null){
            return;
        }

        after(rootNode.getLeftTreeNode());
        after(rootNode.getRightNode());
        System.out.println(rootNode.getValue());

    }

    /**
     * 查找树的深度
     * @param treeNode
     * @return
     */
    public static int height(TreeNode treeNode){
        if(treeNode == null){
            return  0 ;
        }
        //左边深度
        int left = height(treeNode.getLeftTreeNode());
        //右边深度
        int right = height(treeNode.getRightNode());
        int max = left;
        if(right>max){
            max = right;
        }
        return  max+1;
    }
    public static int getMax(TreeNode treeNode){
        if(treeNode == null){
            return  -1;
        }
        //左边最大值
        int left = getMax(treeNode.getLeftTreeNode());
        //右边最大值
        int right = getMax(treeNode.getRightNode());
        //根节点
        int cur = treeNode.getValue();
        //假定左边是最大值
        int max = left;
        if(right > max){
            max = right;
        }
        if(cur > max){
            max = cur;
        }
        return  max;



    }
    public static void main(String[] args) {
        int[]  number = new int[]{12,2,3,4,5,8,12,100,200,1,31,4,6,200};
        System.out.println("创建树");
        RootTree rootTree = new RootTree();
        for(int i : number){
            createTree(rootTree,i);
        }
      TreeNode treeNode = rootTree.getRootTree();
        System.out.println(treeNode);
        System.out.println("------先序遍历----------");
        before(treeNode);
        System.out.println("==========中序遍历=======");
        between(treeNode);
        System.out.println("======后序遍历=========");
        after(treeNode);
        System.out.println("======深度======");
        System.out.println(height(treeNode));
        System.out.println("============获取最大值=========");
        System.out.println(getMax(treeNode));
    }
}
